Efficient calculation of Khinchin's constant
In the previous post we (me, Sander & Sander) set upon ourselves the challenge to beat Xavier Gourdon’s 1997 record of hundred and ten thousand digits of Khinchin’s constant. This quickly diverted into a challenge of calculating the Riemann Zeta function (again, see wikipedia and mathworld for more info).
Khinchin’s constant, $K_0$ and the Zeta function $ζ$ are related by the following identity:
$$ \ln K_0 = \frac{1}{\ln{2}} \sum_{[1,\infty]}^{n} \frac{\zeta(2n) -1}{n} \sum_{[1, 2n-1]}^{k} \frac{(-1)^{k+1}}{k} $$
Analysing bounds and limits
The inner series is an alternating harmonic series and has the following limit:
$$ \lim_{n \to \infty} \sum_{[1, 2n-1]}^{k} \frac{(-1)^{k+1}}{k} = \ln{2} $$
Since we are taking two terms at a time this series it is strictly increasing and $\ln{2}$ is also an upper bound.
An upper bound for $ζ$ can be easily seen from the series definition, $\zeta(2n) - 1 < \frac{2}{2^{2n}}$. Combing these results gives an upper bound for the terms in the outer series:
$$ \frac{\zeta(2n) -1}{n} \sum_{[1, 2n-1]}^{k} \frac{(-1)^{k+1}}{k} < \frac{\ln{4}}{n 4^n} $$
This expression also allows us to calculate an upper bound for the cutoff error, i.e. the error we introduce by not summing to $n=\infty$ but stopping at $n=N$:
$$ \sum_{[N, \infty]} \frac{\ln{4}}{n 4^n} < \ln{4} \sum_{[N, \infty]} \frac{1}{4^n} = \frac{\ln{16}}{3 \cdot 4^N} $$
If we now take the binary logarithm of this number we know how many fractional bits we get at least correct when summing up to $N$. In fact, since $\ln{2} \ln K_0 \approx 1$, we know the total number of bits we get correct:
$$ -\log_2 \left( \frac{\ln{16}}{3 \cdot 4^N} \right) = 2 N + \log_2 3 - \log_2 \ln{16} $$
Or, put differently, to obtain $B$ bits of $K_0$ we must sum up to (but not including):
$$ N =\frac{1}{2}\left(B - \log_2 3 + \log_2 \ln{16}\right) < \left\lceil\frac{B}{2}\right\rceil + 1 $$
The uncertainty of the sum is the sum of the uncertainties of the terms. So if we need an accuracy of $2^{-B}$ for the sum, we can divide this accuracy evenly over the terms, giving each an accuracy of $\frac{1}{N}$ $2^{-B}$. So the precision (in bits) of the terms is:
$$ B_{term} = \left\lceil B + \log_2 N \right\rceil $$
The $ζ$ can be less accurate, since it will be multiplied by $\ln 2 < 1$ and divided by n, this amounts to an required accuracy of:
$$ B_{zeta}(n) = \left\lceil B_{term} - \log_2 n -\log_2 \ln{2} \right\rceil $$
The million digit goal
To calculate $K_0$ accurate up to a million digits we require the following:
Parameter | value |
---|---|
$B$ | 3 321 929 |
$N$ | 1 666 966 |
$B_{term}$ | 3 321 950 |
$B_{zeta}(n)$ | 3 321 951 … 3 321 930 |
The problem can now be restated as: How does one calculate $ζ(2) … ζ(2N)$ fast and accurate up to $B_{zeta}(n)$ bits?